/* $Id: des.c 11 2010-10-20 20:20:47Z dheater@heatertech.com $ */

#include <stdlib.h>
#include "XPRINTF.h"

#define MAX_LINE_SIZE 256
#define NUM_ENTITIES  10


enum event_type_t
{
    ARRIVAL,
    DEPARTURE,
    STOP,
    NUM_EVENT_TYPES
};


static char* event_type_name[NUM_EVENT_TYPES] =
{
    "Arrival",
    "Departure",
    "Stop"
};


enum entity_state_t
{
    PENDING,
    IN_QUEUE,
    IN_SERVICE,
    DEPARTED
};


struct entity
{
    unsigned int id;
    enum entity_state_t state;
    float arrival_time_at_queue;
    float interarrival_time;
    float service_time;
    float arrival_time_at_server;
    float departure_time;
    struct entity* next;
};


enum server_state_t
{
    IDLE,
    BUSY
};


struct event
{
    struct entity* entity;
    enum event_type_t type;
    float time;
    struct event* next;
};


struct des_state
{
    float time;
    enum server_state_t server_state;
    float Qt;
    float Bt;
    struct entity* entities;
    unsigned int num_served;
    unsigned int num_processed_in_queue;
    float total_delay_time;
    float max_delay_time;
    float total_flow_time;
    float max_flow_time;
    float iQt;
    unsigned int max_Qt;
    float iBt;
    struct event* next_event_list;
};


/* Put the new entity at the end of the list.
 */
static void push_entity(struct entity** entities, struct entity* new)
{
    /* Since we only deal with a single list of entities, we can optimize this
     * routine by caching a pointer to the tail of the list.
     */
    static struct entity* p = NULL;

    /* Make sure the tail of the list is terminated.
     */
    new->next = NULL;

    /* Handle first node case.
     */
    if(NULL == p)
    {
        *entities = p = new;
        return;
    }

    /* For all other nodes.
     */
    p->next = new;
    p = new;
}


/* Put event in the list according to time.
 */
static void push_event(struct event** events, struct event* new)
{
    /* Search for the insertion point.
     */
    struct event* p = *events;
    struct event* tmp;
    while((p != NULL) && (p->time < new->time))
    {
        tmp = p;
        p = p->next;
    }

    /* Handle front of the list case.
     */
    if(p == *events)
    {
        new->next = p;
        *events = new;
        return;
    }

    /* Handle end of the line case.
     */
    if(NULL == p)
    {
        new->next = NULL;
        tmp->next = new;
        return;
    }

    /* All other cases.
     */
    new->next = p;
    tmp->next = new;
}


/* Remove the top event from the event list.
 */
static void pop_event(struct event **events)
{
    struct event* p = *events;
    if(NULL == p)
    {
        return;
    }

    *events = p->next;
}


static print_line()
{
    printf("----------------------------------------"
            "----------------------------------------\n");
}


static print_event(struct des_state *state)
{
    static event_number = 1;

    /* The current event points to the first event on the next event list. This
     * pointer is just shorthand to reduce the amount of typing.
     */
    struct event* evt = state->next_event_list;

    /* Output the current event info.
     */
    print_line();
    printf("%s %45s = %u\n", "CURRENT EVENT", "EVENT NUMBER", event_number++);
    printf("%s = %6.2f %15s =", "Time", evt->time, "Entity");
    if(evt->entity)
    {
        printf("%5u", evt->entity->id);
    }
    else
    {
        printf("%4c-", ' ');
    }

    printf("%21s = %s\n", "Event Type", event_type_name[evt->type]);
    printf("\n");

    /* Output the state variables.
     */
    printf("STATE VARIABLES\n");
    printf("%s = %6.2f %13s = %6.2f\n", "Q(t)", state->Qt, "B(t)", state->Bt);
    printf("\n");

    /* Output data for each entity.
     */
    printf("ENTITY ATTRIBUTES\n");
    printf("%s %25s %25s %20s\n", "Entity", "Arrival Time at Queue",
            "Arrival Time at Server", "Departure Time");
    print_line();
    struct entity *ent = state->entities;
    while(ent != NULL)
    {
        printf("%d", ent->id);
        if(ent->state >= IN_QUEUE)
        {
            printf("%21.2f", ent->arrival_time_at_queue);
        }
        if(ent->state >= IN_SERVICE)
        {
            printf("%28.2f", ent->arrival_time_at_server);
        }
        if(ent->state >= DEPARTED)
        {
            printf("%24.2f", ent->departure_time);
        }
        printf("\n");
        ent = ent->next;
    }
    printf("\n");

    /* Output the statistical accumulators.
     */
    printf("STATISTICAL ACCUMULATORS\n");
    printf("%-13s =   %4u %24s = %4u %16s = %6.2f\n",
            "# Served", state->num_served,
            "# Processed in queue", state->num_processed_in_queue,
            "Sum of delays", state->total_delay_time);
    printf("%-13s = %6.2f %21s = %7.2f %16s = %6.2f\n",
            "Max delay", state->max_delay_time,
            "Sum of flow times", state->total_flow_time,
            "Max flow time", state->max_flow_time);
    printf("%s = %6.2f %12s = %16u %16s = %6.2f\n",
            "Integral Q(t)", state->iQt,
            "Max Q(t)", state->max_Qt,
            "Integral B(t)", state->iBt);
    printf("\n");

    /* Output the next event list.
     */
    printf("NEXT-EVENT LIST (EVENT CALANDAR)\n");
    printf("%s %16s %26s %25s\n", "Number", "Time", "Entity", "Event Type");
    print_line();
    unsigned int i = 1;
    while(evt->next != NULL)
    {
        evt = evt->next;
        printf("%u %20.2f", i++, evt->time);
        if(NULL == evt->entity)
        {
            printf("%24c-", ' ');
        }
        else
        {
            printf("%25u", evt->entity->id);
        }
        printf("%27s\n", event_type_name[evt->type]);
    }
    print_line();
    printf("\n\n");
}


void fetch_next_entity(struct des_state* state)
{
    char line[MAX_LINE_SIZE];
    if(NULL == fgets(line, sizeof(line), stdin))
    {
        return;
    }

    /* Allocate memory for the entity.
     */
    struct entity* ent = malloc(sizeof(*ent));
    if(NULL == ent)
    {
        PERROR("malloc");
        return;
    }

    /* Read entity parameters from input data.
     */
    DPRINTF("%s", line);
    sscanf(line,"%d,%f,%f,%f", &ent->id, &ent->arrival_time_at_queue,
            &ent->interarrival_time, &ent->service_time);
    ent->state = PENDING;

    /* Add the entity to the entities list.
     */
    push_entity(&(state->entities), ent);

    /* Create the arrival event.
     */
    struct event* arrival_evt = malloc(sizeof(*arrival_evt));
    if(NULL == arrival_evt)
    {
        PERROR("malloc");
        return;
    }
    arrival_evt->entity = ent;
    arrival_evt->type = ARRIVAL;
    arrival_evt->time = ent->arrival_time_at_queue;

    /* Put arrival event on the next event list.
     */
    push_event(&(state->next_event_list), arrival_evt);
}


static void place_in_service(struct des_state* state, struct entity* ent)
{
    struct event* evt = state->next_event_list;

    ent->state = IN_SERVICE;
    ent->arrival_time_at_server = state->time;
    ++state->num_processed_in_queue;
    state->server_state = BUSY;

    /* Create the departure event.
     */
    struct event* depart_evt = malloc(sizeof(*depart_evt));
    if(NULL == depart_evt)
    {
        PERROR("malloc");
        return;
    }
    depart_evt->entity = ent;
    depart_evt->type = DEPARTURE;
    depart_evt->time = state->time + ent->service_time;
    push_event(&evt, depart_evt);
}


static void update_statistics(struct des_state* state)
{
    static float prev_time = 0.;
    static enum server_state_t prev_server_state = IDLE;
    struct entity* ent = state->entities;
    static unsigned int num_in_queue = 0;

    float elapsed_time = state->time - prev_time;

    /* Update the integral of the queue time. Do this with the count from the
     * previous cycle because that is the total number of entities that have
     * waited in the queue during this time period.
     */
    state->iQt += elapsed_time * num_in_queue;

    /* Update the the amount of time the server has been busy. We use the
     * server's state from the previous iteration to tell us whether she's been
     * busy for this iteration.
     */
    state->iBt += elapsed_time * prev_server_state;

    /* Count how many are in the queue now.
     */
    num_in_queue = 0;
    while(ent != NULL)
    {
        if(IN_QUEUE == ent->state)
        {
            ++num_in_queue;
        }

        ent = ent->next;
    }

    /* Update the maximum queue length if exceeded.
     */
    if(num_in_queue > state->max_Qt)
    {
        state->max_Qt = num_in_queue;
    }

    /* Store states for the next increment.
     */
    prev_time = state->time;
    prev_server_state = state->server_state;
}


static void dispatch_event(struct des_state* state)
{
    struct event* evt = state->next_event_list;
    struct entity* ent = evt->entity;
    state->time = evt->time;

    DPRINTF("Dispatching event type %d\n", evt->type);
    switch(evt->type)
    {
        case ARRIVAL:
            if(IDLE == state->server_state)
            {
                place_in_service(state, ent);
            }
            else
            {
                evt->entity->state = IN_QUEUE;
            }

            fetch_next_entity(state);
            break;
        case DEPARTURE:
            ent->state = DEPARTED;
            ent->departure_time = evt->time;
            state->server_state = IDLE;
            ++state->num_served;

            /* Look at the next entity if one exists.
             */
            if(NULL == ent->next)
            {
                break;
            }

            /* Compute the flow time.
             */
            float flow_time = ent->departure_time - ent->arrival_time_at_queue;

            /* Add to the total flow time.
             */
            state->total_flow_time += flow_time;

            /* Update max flow time if exceeded.
             */
            if(flow_time > state->max_flow_time)
            {
                state->max_flow_time = flow_time;
            }

            /* If the entity is already in the queue, move it into service.
             */
            ent = ent->next;
            if(IN_QUEUE == ent->state)
            {
                place_in_service(state, ent);

                /* Determine delay time.
                 */
                float delay_time = ent->arrival_time_at_server -
                    ent->arrival_time_at_queue;

                /* Update the total delay time.
                 */
                state->total_delay_time += delay_time;

                /* Update max delay time if exceeded.
                 */
                if(delay_time > state->max_delay_time)
                {
                    state->max_delay_time = delay_time;
                }
            }
            break;
        default:
            break;
    }

    update_statistics(state);
    print_event(state);

    /* When we hit the stop event, we're done.
     */
    if(STOP == evt->type)
    {
        exit(0);
    }

    pop_event(&(state->next_event_list));

    dispatch_event(state);
}


int main(int argc, char *argv[])
{
    /* Create the stop event. This is the event that will terminate the
     * simulation.
     */
    struct event* stop = malloc(sizeof(*stop));
    if(NULL == stop)
    {
        PERROR("malloc");
        return -1;
    }

    if(argc < 2)
    {
        printf("Usage: %s stop_time < input_data\n", argv[0]);
        return -1;
    }

    stop->entity = NULL;
    stop->time = strtof(argv[1], NULL);
    stop->type = STOP;
    stop->next = NULL;
    DPRINTF("stop time = %f\n", stop->time);

    /* Initialize the DES state. The stop event is the first event placed on
     * the next event list.
     */
    struct des_state state;
    state.time = 0.;
    state.server_state = IDLE;
    state.Qt = 0.;
    state.Bt = 0.;
    state.entities = NULL;
    state.num_served = 0;
    state.num_processed_in_queue = 0;
    state.total_delay_time = 0.;
    state.max_delay_time = 0.;
    state.total_flow_time = 0.;
    state.max_flow_time = 0.;
    state.iQt = 0.;
    state.max_Qt = 0;
    state.iBt = 0.;
    state.next_event_list = stop;

    float current_time = 0.;

    /* Skip the first line.
     */
    char line[MAX_LINE_SIZE];
    if(NULL == fgets(line, sizeof(line), stdin))
    {
        return;
    }

    fetch_next_entity(&state);

    dispatch_event(&state);

    return 0;
}
